package demo04ArrayListLinkedList;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:咭咭熊
 * Date:2021 - 09 - 13
 * Time:17:09
 */

import java.util.Arrays;

/***
 * 四、顺序表和线性表
 * 1.数据结构：描述和组织数据的方式；数据+ 结构
 *
 * 2.顺序表——底层实际上是一个数组；
 *  优点：空间连续，支持随机访问；
 *
 *  缺点：
 *  （1）中间或者前面部分的插入删除时间复杂度为O(N)；
 *  （2）增容的代价比较大；
 *
 */
public class myArrayList {

    //定义属性；
    private int[] elem;
    private int usedSize;

    public myArrayList(){//通过构造方法初始化变量；
        this.elem = new int[5];
    }
    public myArrayList(int capacity){
        this.elem = new int[capacity];
    }

    public static void main(String[] args) {
        myArrayList list = new myArrayList();
        /*myArrayList list1 = new myArrayList(5);*/
        list.add(0,5);
        list.add(1,15);
        list.add(2,25);
        list.display();

        list.add2(88);
        list.display();
        list.add2(188);
        list.add2(288);
        list.display();

    }



    //1.打印顺序表
    public void display(){
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elem[i] + " ");
        }
        System.out.println();
    }


    /***
     * 判断顺序表是否满了
     * @return
     */
    public boolean isFull(){
        if(this.usedSize == this.elem.length){
            return true;
        }
        return  false;
    }
    /***
     * 2.在pos位置新增元素
     * （1）判断顺序表空或者非空；
     * （2）判断pos位置是否合法；
     * （3）插入数据的时候，此位置之前已预订要有数据；
     * @param pos
     * @param data
     */
    public void add(int pos,int data){
        //(1)判满
        if(isFull()){
            System.out.println("顺序表为满;进行扩容！");
            //顺序表为满的时候，进行扩容
            resize();
            /*return;*/
        }
        //(2)判断pos位置是否合法
        if(pos < 0 || pos > this.usedSize){
            System.out.println("pos位置不合;");
            return;
        }
        //(3)移动元素
        for (int i = this.usedSize; i <= pos  ; i++) {
            elem[i + 1] = elem[i];
        }
        //在pos位置插入数据
        this.elem[pos] = data;
        this.usedSize++;
    }

    /***
     * 扩容:2倍扩容
     */
    private void resize() {

        this.elem = Arrays.copyOf(this.elem,2 * this.elem.length);
    }

    /***
     * 2.1默认将元素插入到顺序表的末尾
     * @param data
     * @return
     */
    public void add2(int data){
        if(isFull()){
            System.out.println("顺序表为满,进行扩容;");
            resize();
            /*return;*/
        }
        this.elem[this.usedSize] = data;
        this.usedSize++;
    }

    //3.判断是否包含某个元素
    public boolean contains(int toFind){
        for (int i = 0; i < this.usedSize; i++) {
            if(this.elem[i] == toFind){
                return true;
            }
        }
        return false;
    }

    //4.查找某个元素对应的位置
    public int search(int toFind){
        for (int i = 0; i < this.usedSize; i++) {
            if(this.elem[i] == toFind){
                return i;
            }
        }
        return  -1;
    }

    //5获取pos位置的元素
    public int getPos(int pos){
        //判断pos位置是否合法
        if(pos < 0 || pos >= this.usedSize){
            System.out.println("pos位置不合法！");
            return -1;
        }
        for (int i = 0; i < usedSize - 1; i++) {
            if(i == pos){
                return elem[i];
            }
        }
        return -1;
    }

    //6.修改pos位置的元素值为value
    public void setPos(int pos,int value){
        //判断pos位置是否合法
        if(pos < 0 || pos >= this.usedSize){
            System.out.println("pos位置不合法！");
            return;
        }
        //将pos位置的值进行修改
        this.elem[pos] = value;


    }

    //7.删除第一次出现的关键字key
    public void remove(int key){

        //(1)查找是否有该元素,设该元素的下标为index
        int index = search(key);//调用search()方法找到该元素的下标
        if(index == -1){
            System.out.println("没有该元素！");
            return;
        }
        //(2)i = index;找出i和usedSize的关系 ：i < usedSize- 1；
        for (int i = index; i < this.usedSize - 1; i++) {
            //覆盖式删除；将后边的元素直接往前移动
            this.elem[i] = this.elem[i + 1];
        }
        //(3)更新顺序表的长度：this.useedSize --;
        this.usedSize --;
    }

    //8.获取顺序表的长度
    public int len(){
        return this.usedSize;
    }

    //9.清空顺序表
    public void clear(){
        this.usedSize = 0;
    }

}
